/**
 * 描述：
 * 6个有序表，ABCDEF，含有10，35，40，50，60，200个元素
 * 表内升序要求通过五次两辆合并，合成一个表
 * 在最坏情况下的比较次数最小
 * 
 * 1. 给出合并过程
 * 每次都找到所有链表中元素个数最小的两个元素合并
 * 如10和35合并尾45
 * 然后是45和40合并为85
 * 40和60合并为110
 * 110和85合并为195
 * 195和200合并为395
 * 比较次数为44+84+109+194+394=825
 * ...
 * 
 * 
 * 2. 描述N个不等长的表的合并策略，说明理由
 * 和上面的同理，参考霍夫曼编码，可以得到此时的合并次数最小
 * 下面是代码实现
 * 本题没有要求代码实现，可以看到如果真要实现代码的化，
 * 需要知道链表中的元素，要么增加类的字段，要么增加很长的count()函数
 * 这样繁琐或者是超出结构体原本定义的题目不会让写代码！！！
 */

#include<map>
#include<iostream>
#include<vector>
using namespace std;

class LinkedList
{
public:
    int data;
    LinkedList* next;
    int n=0;//元素个数

    LinkedList(int d):data(d){};
    LinkedList(int val,LinkedList *n):data(val),next(n),n(1){};
    LinkedList(){};

    void push(int x){
        this->next=new LinkedList(x);
        this->n++;
    }
};
auto merge_two(LinkedList* l1,LinkedList* l2){
    auto head1=l1;
    auto head2=l2;
    auto hair=new LinkedList(0,nullptr);
    auto tail=hair;
    //使用尾插法将两个链表插入到头
    while (head1!=nullptr&&head2!=nullptr)
    {
        if(head1->data<head1->data){
            tail->next=head1;
            tail=tail->next;
            tail->next=head2;
        }else{
            tail->next=head2;
            tail=tail->next;
            tail->next=head1;
        }
        head1=head1->next;
        head2=head2->next;
        tail=tail->next;
    }
    //最后将这两个剩余节点放入尾巴
    if(head1!=nullptr){
        tail->next=head1;
    }
    if(head2!=nullptr){
        tail->next=head2;
    }
    return hair->next;
}
//获取两个最小的节点
pair<int,int> get_min(vector<LinkedList*> lists){
    //同时找最小值和次小值
    int min=INT_MAX;
    int min_index=-1;
    int sub_min=0;
    int sub_min_index=-1;
    for(int i=0;i<lists.size();i++){
        if(lists[i]->n<min){//找到比min还要小的值
            sub_min=min;//先将当前的最小值保存一份
            sub_min_index=min_index;
            min=lists[i]->n;  
            min_index=i;
        };
    }
    //返回最小值和次小值的下标
    return std::bind(sub_min_index,min_index);
}
void merge(vector<LinkedList*> lists){
    
    while (lists.size())
    {
        //选择元素个数最小的两个list
        auto[a,b]=get_min(lists);    
        //合并两个list，到其中的一个
        auto resList=merge_two(lists[a],lists[b]);
        //删除原来的两个list
        lists[a]=nullptr;
        lists[b]=nullptr;
        lists.push_back(resList);
    }
    
}

int main(void){

    return 0;
}